448. Find All Numbers Disappeared in an Array
Easy

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

 

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Accepted
388,388
Submissions
687,362
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
This is a really easy problem if you decide to use additional memory. For those trying to write an initial solution using additional memory, think counters!
Show Hint 2
However, the trick really is to not use any additional space than what is already available to use. Sometimes, multiple passes over the input array help find the solution. However, there's an interesting piece of information in this problem that makes it easy to re-use the input array itself for the solution.
Show Hint 3
The problem specifies that the numbers in the array will be in the range [1, n] where n is the number of elements in the array. Can we use this information and modify the array in-place somehow to find what we need?

Average Rating: 4.79 (47 votes)

Premium

Solution

Approach 1: Using Hash Map

Intuition

The intuition behind using a hash map is pretty clear in this case. We are given that the array would be of size N and it should contain numbers from 1 to N. However, some of the numbers are missing. All we have to do is keep track of which numbers we encounter in the array and then iterate from 1N1 \cdots N and check which numbers did not appear in the hash table. Those will be our missing numbers. Let's look at a formal algorithm based on this idea and then an animation explaining the same with the help of a simple example.

Algorithm

  1. Initialize a hash map, hash to keep track of the numbers that we encounter in the array. Note that we can use a set data structure as well in this case since we are not concerned about the frequency counts of elements.

    Note that for the purposes of illustration, we have use a hash map of size 14 and have ordered the keys of the hash map from 0 to 14. Also, we will be using a simple hash function that directly maps the array entries to their corresponding keys in the hash map. Usually, the mapping is not this simple and is dependent upon the hash function being used in the implementation of the hash map.

  2. Next, iterate over the given array one element at a time and for each element, insert an entry in the hash map. Even if an entry were to exist before in the hash map, it will simply be over-written. For the above example, let's look at the final state of the hash map once we process the last element of the array.

  3. Now that we know the unique set of elements from the array, we can simply find out the missing elements from the range 1N1 \cdots N.

  4. Iterate over all the numbers from 1N1 \cdots N and for each number, check if there's an entry in the hash map. If there is no entry, add that missing number to a result array that we will return from the function eventually.

Current
1 / 9

Complexity Analysis

  • Time Complexity : O(N)O(N)
  • Space Complexity : O(N)O(N)


Approach 2: O(1) Space InPlace Modification Solution

Intuition

We definitely need to keep track of all the unique numbers that appear in the array. However, we don't want to use any extra space for it. This solution that we will look at in just a moment springs from the fact that

All the elements are in the range [1, N]

Since we are given this information, we can make use of the input array itself to somehow mark visited numbers and then find our missing numbers. Now, we don't want to change the actual data in the array but who's stopping us from changing the magnitude of numbers in the array? That is the basic idea behind this algorithm.

We will be negating the numbers seen in the array and use the sign of each of the numbers for finding our missing numbers. We will be treating numbers in the array as indices and mark corresponding locations in the array as negative.

Algorithm

  1. Iterate over the input array one element at a time.
  2. For each element nums[i], mark the element at the corresponding location negative if it's not already marked so i.e. nums[  nums[i]  1  ]×1nums[\; nums[i] \;- 1\;] \times -1 .
  3. Now, loop over numbers from 1N1 \cdots N and for each number check if nums[j] is negative. If it is negative, that means we've seen this number somewhere in the array.
  4. Add all the numbers to the resultant array which don't have their corresponding locations marked as negative in the original array.
Current
1 / 17

Complexity Analysis

  • Time Complexity : O(N)O(N)
  • Space Complexity : O(1)O(1) since we are reusing the input array itself as a hash table and the space occupied by the output array doesn't count toward the space complexity of the algorithm.

Report Article Issue

Comments: 37
lidaivet's avatar
Read More

I like this question.
But the optimal solution is like one of those either you get it right away, or you need some hint.

66
Show 5 replies
Reply
Share
Report
yh32's avatar
Read More

Swapping Solution, O(n) runtime, O(1) space:

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            int idx = nums[i]-1;
            // swap until the nums[i] is at index nums[i]-1
            while(idx != nums[i]){
                swap(nums, idx, i);
                idx = nums[i] - 1;
                // if we are going to swap same number: break
                if(nums[idx] == nums[i]){
                    break;
                }
            }
        }
        // In this point, the array looks like this: [1,2,3,4,3,2,7,8]
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(i != nums[i]-1){
                res.add(i+1);
            }
        }
        
        return res;
    }
    
    private void swap(int[] nums, int idx1, int idx2){
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }
}

17
Show 6 replies
Reply
Share
Report
sjkoo's avatar
Read More

Hmmm.... I feel like this problem could be a medium if it didn't allow anything above O(1) space.

13
Reply
Share
Report
vp393001's avatar
Read More

In the 2nd approach, the existing input array is modified and before returning we are not reverting the changes back. Is it okay?

And in real life development, will it be considered a good practice to modify the present data in order to save space?

8
Show 2 replies
Reply
Share
Report
taejung_chang's avatar
Read More

Personally, I don't find the last approach any smart or useful. Even, it hurts my eyes.

You are basically using the input space as the hash map. There is nothing fancy about it. I would not think of this way because I would never hold my data in such a confusing way. Or, I would not ever mess with the input data/space.

When you make use of the input space to store data, you are technically using the extra space even though you put the original data back. It is like you borrow money from a bank to run a business and telling people that you are running a business for free. Maybe, if you have good credit, you might end up spending no money out of your poker, but, over all, running a business costs money.

How is this kind of solution ever useful or maintainable in production? I truly hope that none of the interviewers, companies, or coding practice platforms ever advocate bad coding practice.

18
Reply
Share
Report
roireshef's avatar
Read More

Python 4-liner O(n) runtime with O(1) space using swapping (without negating, IMHO clearer solution)

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    for idx in range(len(nums)):                       
        while nums[nums[idx]-1] != nums[idx]: # value at target index misplaced
            nums[nums[idx]-1], nums[idx] = nums[idx], nums[nums[idx]-1]  # swap

    return [idx+1 for idx, num in enumerate(nums) if num != idx + 1] 

12
Show 1 reply
Reply
Share
Report
mad-coder's avatar
Read More

Python 1 liner. O(n) time and space complexity

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # 1-liner solution
        return set(range(1,len(nums)+1)) - set(nums)

6
Reply
Share
Report
vineet16's avatar
Read More

Getting to think negating the numbers will not come in first shot though as the original array is being modified.
Negating the numbers is same as modifying the contents of array - so might not be a neat solution.

3
Reply
Share
Report
DawsonDev's avatar
Read More

This is just a set difference {1...n} - {nums} = {missing numbers}. Here's an easy solution in JavaScript:

var findDisappearedNumbers = function(nums) {
    let range = [];
    for (let i = 0; i < nums.length;i++) range.push(i+1);
    return range.filter(x => nums.indexOf(x) < 0);
};

4
Show 2 replies
Reply
Share
Report
AshokaKS's avatar
Read More

C++ solution with 2 FOR loops.
First swap elements which are not in their intended place.
Finally check the missing elements

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        bool modified = true;
        while(modified) {
            modified = false;
            for (int i=0; i<nums.size(); i++) {
                if ((nums[i] != i+1) && (nums[i] != nums[nums[i]-1])) {
                    swap(nums[i], nums[nums[i]-1]);
                    modified = true;
                }
            }
        }
        vector<int> res;
        for (int i=0; i<nums.size(); i++) {
            if (nums[i] != i+1)
                res.push_back(i+1);
        }
        
        return res;
    }
};

1
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
07/28/2020 18:49Accepted132 ms34 MBcpp
05/20/2020 14:27Accepted240 ms35.1 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.